<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-hemisu.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="hemisu">










<meta name="description" content="Just do...">
<meta name="keywords" content="web, 前端, 生活, 分享">
<meta property="og:type" content="website">
<meta property="og:title" content="何米酥`s Blog">
<meta property="og:url" content="http://www.hemisu.com/page/14/index.html">
<meta property="og:site_name" content="何米酥`s Blog">
<meta property="og:description" content="Just do...">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="何米酥`s Blog">
<meta name="twitter:description" content="Just do...">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://www.hemisu.com/page/14/">





  <title>何米酥`s Blog</title>
  








  <!-- Hotjar Tracking Code for www.hemisu.com -->
  <script>
      (function(h,o,t,j,a,r){
          h.hj=h.hj||function(){(h.hj.q=h.hj.q||[]).push(arguments)};
          h._hjSettings={hjid:1933736,hjsv:6};
          a=o.getElementsByTagName('head')[0];
          r=o.createElement('script');r.async=1;
          r.src=t+h._hjSettings.hjid+j+h._hjSettings.hjsv;
          a.appendChild(r);
      })(window,document,'https://static.hotjar.com/c/hotjar-','.js?sv=');
  </script>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">何米酥`s Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">EFE</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/10/123/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/10/123/" itemprop="url">PAT A1043</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-10T15:17:45+00:00">
                2017-02-10
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>给定一个长度不超过10000的、仅由英文字母构成的字符串。请将字符重新调整顺序，按“PATestPATest….”这样的顺序输出，并忽略其它字符。当然，六种字符的个数不一定是一样多的，若某种字符已经输出完，则余下的字符仍按PATest的顺序打印，直到所有字符都被输出。</p>
<p>输入格式：</p>
<p>输入在一行中给出一个长度不超过10000的、仅由英文字母构成的非空字符串。</p>
<p>输出格式：</p>
<p>在一行中按题目要求输出排序后的字符串。题目保证输出非空。</p>
<p>输入样例：<br>redlesPayBestPATTopTeePHPereatitAPPT<br>输出样例：<br>PATestPATestPTetPTePePee</p>
<p>瓜皮代码先来一份：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;algorithm&quot;</span><br><span class="line">//using namespace std;</span><br><span class="line">char str[10010];</span><br><span class="line">int hashTable[6] = &#123;0&#125;;//PATest</span><br><span class="line">char map[6] = &#123;&apos;P&apos;, &apos;A&apos;, &apos;T&apos;, &apos;e&apos;, &apos;s&apos;, &apos;t&apos;&#125;;</span><br><span class="line">int main()&#123;</span><br><span class="line">    gets(str);</span><br><span class="line">    int len = (int)strlen(str);</span><br><span class="line">    for (int i = 0; i &lt; len; i++) &#123;</span><br><span class="line">        switch (str[i]) &#123;</span><br><span class="line">            case &apos;P&apos;:</span><br><span class="line">                hashTable[0]++;</span><br><span class="line">                break;</span><br><span class="line">            case &apos;A&apos;:</span><br><span class="line">                hashTable[1]++;</span><br><span class="line">                break;</span><br><span class="line">            case &apos;T&apos;:</span><br><span class="line">                hashTable[2]++;</span><br><span class="line">                break;</span><br><span class="line">            case &apos;e&apos;:</span><br><span class="line">                hashTable[3]++;</span><br><span class="line">                break;</span><br><span class="line">            case &apos;s&apos;:</span><br><span class="line">                hashTable[4]++;</span><br><span class="line">                break;</span><br><span class="line">            case &apos;t&apos;:</span><br><span class="line">                hashTable[5]++;</span><br><span class="line">                break;</span><br><span class="line">            default:</span><br><span class="line">                break;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int k = 0;//最大的数</span><br><span class="line">    for (int i = 0; i &lt; 6; i++) &#123;</span><br><span class="line">        if (hashTable[i] &gt; hashTable[k]) &#123;</span><br><span class="line">            k = i;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int num = hashTable[k];</span><br><span class="line">    for (int i = 0; i &lt; num; i++) &#123;</span><br><span class="line">        for (int j = 0; j &lt; 6; j++) &#123;</span><br><span class="line">            if (hashTable[j]) &#123;</span><br><span class="line">                printf(&quot;%c&quot;,map[j]);</span><br><span class="line">                hashTable[j]--;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>再来个优化后的：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;algorithm&quot;</span><br><span class="line">//using namespace std;</span><br><span class="line">char str[10010];</span><br><span class="line">int hashTable[6] = &#123;0&#125;;//PATest</span><br><span class="line">char map[6] = &#123;&apos;P&apos;, &apos;A&apos;, &apos;T&apos;, &apos;e&apos;, &apos;s&apos;, &apos;t&apos;&#125;;</span><br><span class="line">int main()&#123;</span><br><span class="line">    gets(str);</span><br><span class="line">    int len = (int)strlen(str), sum;//sum需要输出的字符数</span><br><span class="line">    for (int i = 0; i &lt; len; i++) &#123;</span><br><span class="line">        for (int j = 0; j &lt; 6; j++) &#123;</span><br><span class="line">            if (str[i] == map[j]) &#123;</span><br><span class="line">                hashTable[j]++;</span><br><span class="line">                sum++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    while (sum)&#123;</span><br><span class="line">        for (int j = 0; j &lt; 6; j++) &#123;</span><br><span class="line">            if (hashTable[j]) &#123;</span><br><span class="line">                printf(&quot;%c&quot;,map[j]);</span><br><span class="line">                hashTable[j]--;</span><br><span class="line">                sum--;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/10/122/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/10/122/" itemprop="url">PAT B1042</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-10T15:03:51+00:00">
                2017-02-10
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>请编写程序，找出一段给定文字中出现最频繁的那个英文字母。</p>
<p>输入格式：</p>
<p>输入在一行中给出一个长度不超过1000的字符串。字符串由ASCII码表中任意可见字符及空格组成，至少包含1个英文字母，以回车结束（回车不算在内）。</p>
<p>输出格式：</p>
<p>在一行中输出出现频率最高的那个英文字母及其出现次数，其间以空格分隔。如果有并列，则输出按字母序最小的那个字母。统计时不区分大小写，输出小写字母。</p>
<p>输入样例：<br>This is a simple TEST.  There ARE numbers and other symbols 1&amp;2&amp;3………..<br>输出样例：<br>e 7<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;algorithm&quot;</span><br><span class="line">//using namespace std;</span><br><span class="line">char str[1010];</span><br><span class="line">int hashTable[30] = &#123;0&#125;;</span><br><span class="line">int main()&#123;</span><br><span class="line">    gets(str);</span><br><span class="line">    int len = (int)strlen(str);</span><br><span class="line">    for (int i = 0; i &lt; len; i++) &#123;</span><br><span class="line">        if (str[i] &gt;= &apos;a&apos; &amp;&amp; str[i] &lt;= &apos;z&apos;) &#123;</span><br><span class="line">            hashTable[str[i] - &apos;a&apos; ]++;//统计不区分大小写</span><br><span class="line">        &#125;else if ( str[i] &gt;= &apos;A&apos; &amp;&amp; str[i] &lt;= &apos;Z&apos;)&#123;</span><br><span class="line">            hashTable[str[i] - &apos;A&apos; ]++;//统计不区分大小写</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int k = 0;//记录数组中最大的元素的下标</span><br><span class="line">    for(int i = 0; i &lt; 26; i++)&#123;</span><br><span class="line">        if(hashTable[i] &gt; hashTable[k])</span><br><span class="line">            k = i;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%c %d\n&quot;, &apos;a&apos; + k, hashTable[k]);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/10/121/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/10/121/" itemprop="url">PAT B1039/A1092</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-10T15:02:26+00:00">
                2017-02-10
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>小红想买些珠子做一串自己喜欢的珠串。卖珠子的摊主有很多串五颜六色的珠串，但是不肯把任何一串拆散了卖。于是小红要你帮忙判断一下，某串珠子里是否包含了全部自己想要的珠子？如果是，那么告诉她有多少多余的珠子；如果不是，那么告诉她缺了多少珠子。</p>
<p>为方便起见，我们用[0-9]、[a-z]、[A-Z]范围内的字符来表示颜色。例如在图1中，第3串是小红想做的珠串；那么第1串可以买，因为包含了全部她想要的珠子，还多了8颗不需要的珠子；第2串不能买，因为没有黑色珠子，并且少了一颗红色的珠子。</p>
<p>图 1<br>输入格式：</p>
<p>每个输入包含1个测试用例。每个测试用例分别在2行中先后给出摊主的珠串和小红想做的珠串，两串都不超过1000个珠子。</p>
<p>输出格式：</p>
<p>如果可以买，则在一行中输出“Yes”以及有多少多余的珠子；如果不可以买，则在一行中输出“No”以及缺了多少珠子。其间以1个空格分隔。</p>
<p>输入样例1：<br>ppRYYGrrYBR2258<br>YrR8RrY<br>输出样例1：<br>Yes 8<br>输入样例2：<br>ppRYYGrrYB225<br>YrR8RrY<br>输出样例2：<br>No 2</p>
<p>Eva would like to make a string of beads with her favorite colors so she went to a small shop to buy some beads. There were many colorful strings of beads. However the owner of the shop would only sell the strings in whole pieces. Hence Eva must check whether a string in the shop contains all the beads she needs. She now comes to you for help: if the answer is “Yes”, please tell her the number of extra beads she has to buy; or if the answer is “No”, please tell her the number of beads missing from the string.</p>
<p>For the sake of simplicity, let’s use the characters in the ranges [0-9], [a-z], and [A-Z] to represent the colors. For example, the 3rd string in Figure 1 is the one that Eva would like to make. Then the 1st string is okay since it contains all the necessary beads with 8 extra ones; yet the 2nd one is not since there is no black bead and one less red bead.</p>
<p>Figure 1<br>Input Specification:</p>
<p>Each input file contains one test case. Each case gives in two lines the strings of no more than 1000 beads which belong to the shop owner and Eva, respectively.</p>
<p>Output Specification:</p>
<p>For each test case, print your answer in one line. If the answer is “Yes”, then also output the number of extra beads Eva has to buy; or if the answer is “No”, then also output the number of beads missing from the string. There must be exactly 1 space between the answer and the number.</p>
<p>Sample Input 1:<br>ppRYYGrrYBR2258<br>YrR8RrY<br>Sample Output 1:<br>Yes 8<br>Sample Input 2:<br>ppRYYGrrYB225<br>YrR8RrY<br>Sample Output 1:<br>No 2<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">int hashTable[80] = &#123;0&#125;,miss = 0;</span><br><span class="line">int change(char c)&#123;</span><br><span class="line">    if (c &gt;= &apos;0&apos; &amp;&amp; c &lt;= &apos;9&apos;) return c - &apos;0&apos;;</span><br><span class="line">    if (c &gt;= &apos;a&apos; &amp;&amp; c &lt;= &apos;z&apos;) return c - &apos;a&apos; + 10;</span><br><span class="line">    if (c &gt;= &apos;A&apos; &amp;&amp; c &lt;= &apos;Z&apos;) return c - &apos;A&apos; + 36;</span><br><span class="line">    else return -1;</span><br><span class="line">&#125;</span><br><span class="line">char str1[1010], str2[1010];</span><br><span class="line">int main()&#123;</span><br><span class="line">    gets(str1);</span><br><span class="line">    gets(str2);</span><br><span class="line">    int len1 = (int)strlen(str1);</span><br><span class="line">    int len2 = (int)strlen(str2);</span><br><span class="line">    for (int i = 0; i &lt; len1; i++) &#123;</span><br><span class="line">        int id = change(str1[i]);</span><br><span class="line">        hashTable[id]++;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; len2; i++) &#123;</span><br><span class="line">        int id = change(str2[i]);</span><br><span class="line">        hashTable[id]--;//需要的珠子从hash表减掉</span><br><span class="line">        if (hashTable[id] &lt; 0) &#123;</span><br><span class="line">            miss++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    if (miss &gt; 0) &#123;</span><br><span class="line">        printf(&quot;No %d\n&quot;, miss);</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        printf(&quot;Yes %d\n&quot;,len1 - len2);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/10/120/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/10/120/" itemprop="url">PAT B1038</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-10T13:56:08+00:00">
                2017-02-10
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>本题要求读入N名学生的成绩，将获得某一给定分数的学生人数输出。</p>
<p>输入格式：</p>
<p>输入在第1行给出不超过105的正整数N，即学生总人数。随后1行给出N名学生的百分制整数成绩，中间以空格分隔。最后1行给出要查询的分数个数K（不超过N的正整数），随后是K个分数，中间以空格分隔。</p>
<p>输出格式：</p>
<p>在一行中按查询顺序给出得分等于指定分数的学生人数，中间以空格分隔，但行末不得有多余空格。</p>
<p>输入样例：<br>10<br>60 75 90 55 75 99 82 90 75 50<br>3 75 90 88<br>输出样例：<br>3 2 0<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">int Hashtable[110] = &#123;0&#125;;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n,temp;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    while (n--) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;temp);</span><br><span class="line">        Hashtable[temp]++;</span><br><span class="line">    &#125;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    while (n--) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;temp);</span><br><span class="line">        printf(&quot;%d&quot;, Hashtable[temp]);</span><br><span class="line">        if (n) &#123;</span><br><span class="line">            printf(&quot; &quot;);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/10/119/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/10/119/" itemprop="url">PAT B1033</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-10T13:01:59+00:00">
                2017-02-10
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及坏掉的那些键，打出的结果文字会是怎样？</p>
<p>输入格式：</p>
<p>输入在2行中分别给出坏掉的那些键、以及应该输入的文字。其中对应英文字母的坏键以大写给出；每段文字是不超过105个字符的串。可用的字符包括字母[a-z, A-Z]、数字0-9、以及下划线“_”（代表空格）、“,”、“.”、“-”、“+”（代表上档键）。题目保证第2行输入的文字串非空。</p>
<p>注意：如果上档键坏掉了，那么大写的英文字母无法被打出。</p>
<p>输出格式：</p>
<p>在一行中输出能够被打出的结果文字。如果没有一个字符能被打出，则输出空行。</p>
<p>输入样例：<br>7+IE.<br>7_This_is_a_test.<br>输出样例：<br>_hs_s_a_tst<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">char str1[100010], str2[100010];</span><br><span class="line">int main()&#123;</span><br><span class="line">    bool Hashtable[256];//默认都可以打出</span><br><span class="line">    memset(Hashtable, true, sizeof(Hashtable));</span><br><span class="line">    gets(str1);</span><br><span class="line">    gets(str2);</span><br><span class="line">    int len1 = (int)strlen(str1);</span><br><span class="line">    int len2 = (int)strlen(str2);</span><br><span class="line">    for (int i = 0 ; i &lt; len1; i++) &#123;</span><br><span class="line">        if (str1[i] &gt;= &apos;A&apos; &amp;&amp; str1[i] &lt;= &apos;Z&apos;) &#123;</span><br><span class="line">            str1[i] = str1[i] - &apos;A&apos; + &apos;a&apos;;</span><br><span class="line">        &#125;</span><br><span class="line">        Hashtable[str1[i]] = false;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0 ; i &lt; len2; i++) &#123;</span><br><span class="line">        if (str2[i] &gt;= &apos;A&apos; &amp;&amp; str2[i] &lt;= &apos;Z&apos;) &#123;</span><br><span class="line">            int low = str2[i] - &apos;A&apos; + &apos;a&apos;;</span><br><span class="line">            if (Hashtable[low] == true &amp;&amp; Hashtable[&apos;+&apos;] == true) &#123;</span><br><span class="line">                printf(&quot;%c&quot;, str2[i]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;else if (Hashtable[str2[i]] == true)&#123;</span><br><span class="line">            printf(&quot;%c&quot;, str2[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;\n&quot;);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/10/118/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/10/118/" itemprop="url">PAT B1029/A1084</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-10T13:00:35+00:00">
                2017-02-10
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。</p>
<p>输入格式：</p>
<p>输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。</p>
<p>输出格式：</p>
<p>按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。</p>
<p>输入样例：<br>7_This_is_a_test<br>_hs_s_a_es<br>输出样例：<br>7TI</p>
<p>On a broken keyboard, some of the keys are worn out. So when you type some sentences, the characters corresponding to those keys will not appear on screen.</p>
<p>Now given a string that you are supposed to type, and the string that you actually type out, please list those keys which are for sure worn out.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the 1st line contains the original string, and the 2nd line contains the typed-out string. Each string contains no more than 80 characters which are either English letters [A-Z] (case insensitive), digital numbers [0-9], or “_” (representing the space). It is guaranteed that both strings are non-empty.</p>
<p>Output Specification:</p>
<p>For each test case, print in one line the keys that are worn out, in the order of being detected. The English letters must be capitalized. Each worn out key must be printed once only. It is guaranteed that there is at least one worn out key.</p>
<p>Sample Input:<br>7_This_is_a_test<br>_hs_s_a_es<br>Sample Output:<br>7TI</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">int main()&#123;</span><br><span class="line">    char str1[100], str2[100];</span><br><span class="line">    bool Hashtable[128] = &#123;false&#125;;</span><br><span class="line">    scanf(&quot;%s%s&quot;, str1,str2);</span><br><span class="line">    int len1 = (int)strlen(str1);</span><br><span class="line">    int len2 = (int)strlen(str2);</span><br><span class="line">    for (int i = 0 ; i &lt; len1; i++) &#123;</span><br><span class="line">        int j;</span><br><span class="line">        char c1, c2;</span><br><span class="line">        for (j = 0; j &lt; len2; j++) &#123;</span><br><span class="line">            c1 = str1[i];</span><br><span class="line">            c2 = str2[j];</span><br><span class="line">            if (c1 &gt;= &apos;a&apos; &amp;&amp; c1 &lt;= &apos;z&apos;) &#123;</span><br><span class="line">                c1 -= 32;//如果是小写字母，转化为大写</span><br><span class="line">            &#125;</span><br><span class="line">            if (c2 &gt;= &apos;a&apos; &amp;&amp; c2 &lt;= &apos;z&apos;) &#123;</span><br><span class="line">                c2 -= 32;</span><br><span class="line">            &#125;</span><br><span class="line">            if (c1 == c2) &#123;</span><br><span class="line">                break;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        if (j == len2 &amp;&amp; Hashtable[c1] == false) &#123;</span><br><span class="line">            printf(&quot;%c&quot; , c1);//c1不在str2中且没有被输出过</span><br><span class="line">            Hashtable[c1] = true;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/09/117/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/09/117/" itemprop="url">PAT A1080</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-09T22:51:55+00:00">
                2017-02-09
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>It is said that in 2013, there were about 100 graduate schools ready to proceed over 40,000 applications in Zhejiang Province. It would help a lot if you could write a program to automate the admission procedure.</p>
<p>Each applicant will have to provide two grades: the national entrance exam grade GE, and the interview grade GI. The final grade of an applicant is (GE + GI) / 2. The admission rules are:</p>
<p>The applicants are ranked according to their final grades, and will be admitted one by one from the top of the rank list.<br>If there is a tied final grade, the applicants will be ranked according to their national entrance exam grade GE. If still tied, their ranks must be the same.<br>Each applicant may have K choices and the admission will be done according to his/her choices: if according to the rank list, it is one’s turn to be admitted; and if the quota of one’s most preferred shcool is not exceeded, then one will be admitted to this school, or one’s other choices will be considered one by one in order. If one gets rejected by all of preferred schools, then this unfortunate applicant will be rejected.<br>If there is a tied rank, and if the corresponding applicants are applying to the same school, then that school must admit all the applicants with the same rank, even if its quota will be exceeded.<br>Input Specification:</p>
<p>Each input file contains one test case. Each case starts with a line containing three positive integers: N (&lt;=40,000), the total number of applicants; M (&lt;=100), the total number of graduate schools; and K (&lt;=5), the number of choices an applicant may have.</p>
<p>In the next line, separated by a space, there are M positive integers. The i-th integer is the quota of the i-th graduate school respectively.</p>
<p>Then N lines follow, each contains 2+K integers separated by a space. The first 2 integers are the applicant’s GE and GI, respectively. The next K integers represent the preferred schools. For the sake of simplicity, we assume that the schools are numbered from 0 to M-1, and the applicants are numbered from 0 to N-1.</p>
<p>Output Specification:</p>
<p>For each test case you should output the admission results for all the graduate schools. The results of each school must occupy a line, which contains the applicants’ numbers that school admits. The numbers must be in increasing order and be separated by a space. There must be no extra space at the end of each line. If no applicant is admitted by a school, you must output an empty line correspondingly.</p>
<p>Sample Input:<br>11 6 3<br>2 1 2 2 2 3<br>100 100 0 1 2<br>60 60 2 3 5<br>100 90 0 3 4<br>90 100 1 2 0<br>90 90 5 1 3<br>80 90 1 0 2<br>80 80 0 1 2<br>80 80 0 1 2<br>80 70 1 3 2<br>70 80 1 2 3<br>100 100 0 2 4<br>Sample Output:<br>0 10<br>3<br>5 6 7<br>2 8</p>
<p>1 4<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">struct student&#123;</span><br><span class="line">    int stuid, ge, gi, sum;</span><br><span class="line">    int choice[6];//录取意向</span><br><span class="line">    int rank;//排名</span><br><span class="line">&#125;stu[40010];</span><br><span class="line">struct school&#123;</span><br><span class="line">    int quota;</span><br><span class="line">    int stuNum;</span><br><span class="line">    int id[40010];//招收学生的学号</span><br><span class="line">    int lastAdmit;</span><br><span class="line">&#125;sch[110];</span><br><span class="line">int n,m,k;</span><br><span class="line">bool cmp(student a, student b)&#123;</span><br><span class="line">    if (a.sum != b.sum) &#123;</span><br><span class="line">        return a.sum &gt; b.sum;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        return a.ge &gt; b.ge;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">bool cmpid(int a, int b)&#123;</span><br><span class="line">    return stu[a].stuid &lt; stu[b].stuid;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d%d&quot;, &amp;n, &amp;m, &amp;k);</span><br><span class="line">    for (int i = 0; i &lt; m; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;sch[i].quota);</span><br><span class="line">        sch[i].stuNum = 0;</span><br><span class="line">        sch[i].lastAdmit = -1;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0 ; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;stu[i].ge, &amp;stu[i].gi);</span><br><span class="line">        stu[i].stuid = i;</span><br><span class="line">        stu[i].sum = stu[i].gi + stu[i].ge;</span><br><span class="line">        for (int j = 0; j &lt; k; j++) &#123;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;stu[i].choice[j]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    sort(stu, stu + n, cmp);</span><br><span class="line">    //进行排名</span><br><span class="line">    stu[0].rank = 1;</span><br><span class="line">    for (int r = 1; r &lt; n; r++) &#123;</span><br><span class="line">        if (stu[r].sum == stu[r - 1].sum &amp;&amp; stu[r].ge == stu[r - 1].ge) &#123;</span><br><span class="line">            //相同排名</span><br><span class="line">            stu[r].rank = stu[r - 1].rank;</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            stu[r].rank = r + 1;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    //分配学校</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        //对每个学生判断被哪个学校录取</span><br><span class="line">        for (int j = 0 ; j &lt; k; j++) &#123;</span><br><span class="line">            int choice = stu[i].choice[j];</span><br><span class="line">            int num = sch[choice].stuNum;//学校的当前招生人数</span><br><span class="line">            int last = sch[choice].lastAdmit;//最后一个录取的学生的学号</span><br><span class="line">            if (num &lt; sch[choice].quota || (last != -1 &amp;&amp; stu[i].rank == stu[last].rank)) &#123;</span><br><span class="line">                //还有名额剩余或者前一个同学和后一个同学排名相同</span><br><span class="line">                sch[choice].id[num] = i;//记录该考生</span><br><span class="line">                sch[choice].lastAdmit = i;</span><br><span class="line">                sch[choice].stuNum++;//当前招生人数+1</span><br><span class="line">                break;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; m; i++) &#123;</span><br><span class="line">        if (sch[i].stuNum &gt; 0) &#123;//招到了学生</span><br><span class="line">            sort(sch[i].id, sch[i].id + sch[i].stuNum, cmpid);//按id排序</span><br><span class="line">            for (int j = 0; j &lt; sch[i].stuNum; j++) &#123;</span><br><span class="line">                printf(&quot;%d&quot;,stu[sch[i].id[j]].stuid);</span><br><span class="line">                if (j &lt; sch[i].stuNum - 1) &#123;</span><br><span class="line">                    printf(&quot; &quot;);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        printf(&quot;\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/09/116/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/09/116/" itemprop="url">PAT A1083</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-09T22:09:48+00:00">
                2017-02-09
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given a list of N student records with name, ID and grade. You are supposed to sort the records with respect to the grade in non-increasing order, and output those student records of which the grades are in a given interval.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. Each case is given in the following format:</p>
<p>N<br>name[1] ID[1] grade[1]<br>name[2] ID[2] grade[2]<br>… …<br>name[N] ID[N] grade[N]<br>grade1 grade2<br>where name[i] and ID[i] are strings of no more than 10 characters with no space, grade[i] is an integer in [0, 100], grade1 and grade2 are the boundaries of the grade’s interval. It is guaranteed that all the grades are distinct.</p>
<p>Output Specification:</p>
<p>For each test case you should output the student records of which the grades are in the given interval [grade1, grade2] and are in non-increasing order. Each student record occupies a line with the student’s name and ID, separated by one space. If there is no student’s grade in that interval, output “NONE” instead.</p>
<p>Sample Input 1:<br>4<br>Tom CS000001 59<br>Joe Math990112 89<br>Mike CS991301 100<br>Mary EE990830 95<br>60 100<br>Sample Output 1:<br>Mike CS991301<br>Mary EE990830<br>Joe Math990112<br>Sample Input 2:<br>2<br>Jean AA980920 60<br>Ann CS01 80<br>90 95<br>Sample Output 2:<br>NONE<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">struct student&#123;</span><br><span class="line">    char name[15];</span><br><span class="line">    char id[15];</span><br><span class="line">    int grade;</span><br><span class="line">&#125;stu[1010];</span><br><span class="line">bool cmp(student a, student b)&#123;</span><br><span class="line">    return a.grade &gt; b.grade;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, grade1, grade2;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 0 ; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%s%s%d&quot;, stu[i].name, stu[i].id, &amp;stu[i].grade);</span><br><span class="line">    &#125;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;grade1, &amp;grade2);</span><br><span class="line">    sort(stu, stu + n, cmp);</span><br><span class="line">    int cnt = 0;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        if (stu[i].grade &gt;= grade1 &amp;&amp; stu[i].grade &lt;= grade2) &#123;</span><br><span class="line">            printf(&quot;%s %s\n&quot;, stu[i].name, stu[i].id);</span><br><span class="line">            cnt++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    if (cnt == 0) &#123;</span><br><span class="line">        printf(&quot;NONE\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>NONE后面居然还要换行符 无语。。</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/09/115/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/09/115/" itemprop="url">PAT A1075</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-09T16:55:11+00:00">
                2017-02-09
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>The ranklist of PAT is generated from the status list, which shows the scores of the submittions. This time you are supposed to generate the ranklist for PAT.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 3 positive integers, N (&lt;=104), the total number of users, K (&lt;=5), the total number of problems, and M (&lt;=105), the total number of submittions. It is then assumed that the user id’s are 5-digit numbers from 00001 to N, and the problem id’s are from 1 to K. The next line contains K positive integers p[i] (i=1, …, K), where p[i] corresponds to the full mark of the i-th problem. Then M lines follow, each gives the information of a submittion in the following format:</p>
<p>user_id problem_id partial_score_obtained</p>
<p>where partial_score_obtained is either -1 if the submittion cannot even pass the compiler, or is an integer in the range [0, p[problem_id]]. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, you are supposed to output the ranklist in the following format:</p>
<p>rank user_id total_score s[1] … s[K]</p>
<p>where rank is calculated according to the total_score, and all the users with the same total_score obtain the same rank; and s[i] is the partial score obtained for the i-th problem. If a user has never submitted a solution for a problem, then “-“ must be printed at the corresponding position. If a user has submitted several solutions to solve one problem, then the highest score will be counted.</p>
<p>The ranklist must be printed in non-decreasing order of the ranks. For those who have the same rank, users must be sorted in nonincreasing order according to the number of perfectly solved problems. And if there is still a tie, then they must be printed in increasing order of their id’s. For those who has never submitted any solution that can pass the compiler, or has never submitted any solution, they must NOT be shown on the ranklist. It is guaranteed that at least one user can be shown on the ranklist.</p>
<p>Sample Input:<br>7 4 20<br>20 25 25 30<br>00002 2 12<br>00007 4 17<br>00005 1 19<br>00007 2 25<br>00005 1 20<br>00002 2 2<br>00005 1 15<br>00001 1 18<br>00004 3 25<br>00002 2 25<br>00005 3 22<br>00006 4 -1<br>00001 2 18<br>00002 1 20<br>00004 1 15<br>00002 4 18<br>00001 3 4<br>00001 4 2<br>00005 2 -1<br>00004 2 0<br>Sample Output:<br>1 00002 63 20 25 - 18<br>2 00005 42 20 0 22 -<br>2 00007 42 - 25 - 17<br>2 00001 42 18 18 4 2<br>5 00004 40 15 0 25 -</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">struct student&#123;</span><br><span class="line">    int id;</span><br><span class="line">    int score[6];</span><br><span class="line">    bool flag;//是否有能通过编译的提交</span><br><span class="line">    int score_all;</span><br><span class="line">    int solve;//满分题数</span><br><span class="line">&#125;stu[10010];</span><br><span class="line">int full[6];</span><br><span class="line">int n, k ,m;</span><br><span class="line">bool cmp (student a, student b)&#123;</span><br><span class="line">    if (a.score_all != b.score_all) &#123;</span><br><span class="line">        return a.score_all &gt; b.score_all;</span><br><span class="line">    &#125;else if (a.solve != b.solve)&#123;</span><br><span class="line">        return a.solve &gt; b.solve;</span><br><span class="line">    &#125;return a.id &lt; b.id;</span><br><span class="line">&#125;</span><br><span class="line">void init()&#123;</span><br><span class="line">    for (int i = 1; i &lt;=n; i++) &#123;</span><br><span class="line">        stu[i].id = i;</span><br><span class="line">        stu[i].score_all = 0;</span><br><span class="line">        stu[i].solve = 0;</span><br><span class="line">        stu[i].flag = false;</span><br><span class="line">        memset(stu[i].score, -1, sizeof(stu[i].score));</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d%d&quot;, &amp;n, &amp;k, &amp;m);</span><br><span class="line">    init();</span><br><span class="line">    for (int i = 1 ; i &lt;= k ; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;full[i]);//读取分数</span><br><span class="line">    &#125;</span><br><span class="line">    int u_id, p_id, score_obtained;//考生ID，题目ID，所获分值</span><br><span class="line">    for (int i = 0; i &lt; m; i++) &#123;</span><br><span class="line">        scanf(&quot;%d%d%d&quot;, &amp;u_id, &amp;p_id, &amp;score_obtained);</span><br><span class="line">        if (score_obtained != -1) &#123;</span><br><span class="line">            //通过编译</span><br><span class="line">            stu[u_id].flag = true;</span><br><span class="line">        &#125;</span><br><span class="line">        if (score_obtained == -1 &amp;&amp; stu[u_id].score[p_id] == -1) &#123;</span><br><span class="line">            //某题编译错误，分值记为0，便于输出</span><br><span class="line">            stu[u_id].score[p_id] = 0;</span><br><span class="line">        &#125;</span><br><span class="line">        if (score_obtained == full[p_id] &amp;&amp; stu[u_id].score[p_id] &lt; full[p_id]) &#123;</span><br><span class="line">            //某一题获得了满分</span><br><span class="line">            stu[u_id].solve++;</span><br><span class="line">        &#125;</span><br><span class="line">        if (score_obtained &gt; stu[u_id].score[p_id]) &#123;</span><br><span class="line">            //某题获得了更高的分数</span><br><span class="line">            stu[u_id].score[p_id] = score_obtained;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        for (int j = 1; j &lt;= k; j++) &#123;</span><br><span class="line">            if (stu[i].score[j] != -1) &#123;</span><br><span class="line">                //计算总分</span><br><span class="line">                stu[i].score_all += stu[i].score[j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    sort(stu + 1, stu + n + 1, cmp);</span><br><span class="line">    int r = 1;//当前排名</span><br><span class="line">    for (int i = 1; i &lt;= n &amp;&amp; stu[i].flag == true; i++) &#123;</span><br><span class="line">        if (i &gt; 1 &amp;&amp; stu[i].score_all != stu[i - 1].score_all) &#123;</span><br><span class="line">            r = i;</span><br><span class="line">        &#125;</span><br><span class="line">        printf(&quot;%d %05d %d&quot;, r, stu[i].id, stu[i].score_all );</span><br><span class="line">        for (int j = 1; j &lt;= k; j++) &#123;</span><br><span class="line">            if (stu[i].score[j] == -1) &#123;</span><br><span class="line">                printf(&quot; -&quot;);//没有提交 显示-</span><br><span class="line">            &#125;else&#123;</span><br><span class="line">                printf(&quot; %d&quot;, stu[i].score[j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        printf(&quot;\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/09/114/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/09/114/" itemprop="url">PAT A1055</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-09T15:30:54+00:00">
                2017-02-09
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Forbes magazine publishes every year its list of billionaires based on the annual ranking of the world’s wealthiest people. Now you are supposed to simulate this job, but concentrate only on the people in a certain range of ages. That is, given the net worths of N people, you must find the M richest people in a given range of their ages.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 2 positive integers: N (&lt;=105) - the total number of people, and K (&lt;=103) - the number of queries. Then N lines follow, each contains the name (string of no more than 8 characters without space), age (integer in (0, 200]), and the net worth (integer in [-106, 106]) of a person. Finally there are K lines of queries, each contains three positive integers: M (&lt;= 100) - the maximum number of outputs, and [Amin, Amax] which are the range of ages. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each query, first print in a line “Case #X:” where X is the query number starting from 1. Then output the M richest people with their ages in the range [Amin, Amax]. Each person’s information occupies a line, in the format</p>
<p>Name Age Net_Worth<br>The outputs must be in non-increasing order of the net worths. In case there are equal worths, it must be in non-decreasing order of the ages. If both worths and ages are the same, then the output must be in non-decreasing alphabetical order of the names. It is guaranteed that there is no two persons share all the same of the three pieces of information. In case no one is found, output “None”.<br>Sample Input:<br>12 4<br>Zoe_Bill 35 2333<br>Bob_Volk 24 5888<br>Anny_Cin 95 999999<br>Williams 30 -22<br>Cindy 76 76000<br>Alice 18 88888<br>Joe_Mike 32 3222<br>Michael 5 300000<br>Rosemary 40 5888<br>Dobby 24 5888<br>Billy 24 5888<br>Nobody 5 0<br>4 15 45<br>4 30 35<br>4 5 95<br>1 45 50<br>Sample Output:<br>Case #1:<br>Alice 18 88888<br>Billy 24 5888<br>Bob_Volk 24 5888<br>Dobby 24 5888<br>Case #2:<br>Joe_Mike 32 3222<br>Zoe_Bill 35 2333<br>Williams 30 -22<br>Case #3:<br>Anny_Cin 95 999999<br>Michael 5 300000<br>Alice 18 88888<br>Cindy 76 76000<br>Case #4:<br>None<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">struct person&#123;</span><br><span class="line">    char name[10];</span><br><span class="line">    int age;</span><br><span class="line">    int worth;</span><br><span class="line">&#125;ps[100010],valid[100010];</span><br><span class="line">int age[100010] = &#123;0&#125;;</span><br><span class="line">bool cmp (person a, person b)&#123;</span><br><span class="line">    if (a.worth != b.worth) &#123;</span><br><span class="line">        return a.worth &gt; b.worth;</span><br><span class="line">    &#125;else if(a.age != b.age)&#123;</span><br><span class="line">        return a.age &lt; b .age;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        return strcmp(a.name, b.name) &lt; 0;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, k;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;k);</span><br><span class="line">    for (int i = 0 ; i &lt; n ; i++) &#123;</span><br><span class="line">        scanf(&quot;%s%d%d&quot;, ps[i].name, &amp;ps[i].age, &amp;ps[i].worth);</span><br><span class="line">    &#125;</span><br><span class="line">    sort(ps, ps + n, cmp);</span><br><span class="line">    int validnum = 0;//预处理 每个年龄不超过100人</span><br><span class="line">    for (int i = 0 ; i &lt; n ; i++) &#123;</span><br><span class="line">        if (age[ps[i].age] &lt; 100) &#123;</span><br><span class="line">            age[ps[i].age]++;</span><br><span class="line">            valid[validnum++] = ps[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int m, agelow, agehigh;</span><br><span class="line">    for (int i = 1 ; i &lt;= k ; i++) &#123;</span><br><span class="line">        scanf(&quot;%d%d%d&quot;, &amp;m, &amp;agelow, &amp;agehigh);</span><br><span class="line">        printf(&quot;Case #%d:\n&quot;, i);</span><br><span class="line">        int printnum = 0;</span><br><span class="line">        for (int j = 0 ; j &lt; validnum &amp;&amp; printnum &lt; m; j++) &#123;</span><br><span class="line">            if (valid[j].age &gt;= agelow &amp;&amp; valid[j].age &lt;= agehigh) &#123;</span><br><span class="line">                printf(&quot;%s %d %d\n&quot;,valid[j].name, valid[j].age, valid[j].worth);</span><br><span class="line">                printnum++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        if (printnum == 0) &#123;</span><br><span class="line">            printf(&quot;None\n&quot;);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>本题需要进行预处理，同年龄的超过100人就不用再记录到新的数组中了，减少时间复杂度。</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/page/13/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/13/">13</a><span class="page-number current">14</span><a class="page-number" href="/page/15/">15</a><span class="space">&hellip;</span><a class="page-number" href="/page/21/">21</a><a class="extend next" rel="next" href="/page/15/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/avatar.jpg" alt="何米酥">
            
              <p class="site-author-name" itemprop="name">何米酥</p>
              <p class="site-description motion-element" itemprop="description">Just do...</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">202</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">78</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/hemisu" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.zhihu.com/people/hemisu" target="_blank" title="知乎">
                      
                        <i class="fa fa-fw fa-globe"></i>知乎</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2015 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">何米酥</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
